package com.lfg.leetcode.leetcode0;

public class No86partition {

    public static void main(String[] args) {
        ListNode ret = partition(ListNode.deserialize("[6,5,4,3,2,1,2,3,4,5,6,7,8,9]"), 6);
        while (ret != null) {
            System.out.println("[" + ret.val + "]");
            ret = ret.next;
        }
    }

    public static ListNode partition(ListNode head, int x) {
        ListNode lessThan = null;
        ListNode greatThan = null;
        ListNode greatThanTail = null;
        ListNode lessThanTail = null;
        while (head != null) {
            if (head.val < x) {
                if (lessThan == null) {
                    lessThan = head;
                    lessThanTail = head;
                } else {
                    lessThanTail.next = head;
                    lessThanTail = lessThanTail.next;
                }
            } else {
                if (greatThan == null) {
                    greatThan = head;
                    greatThanTail = greatThan;
                } else {
                    greatThanTail.next = head;
                    greatThanTail = greatThanTail.next;
                }
            }
            head = head.next;
        }
        if (null == greatThanTail) {
            return lessThan;
        }
        greatThanTail.next = null;
        if (null == lessThanTail) {
            return greatThan;
        }

        lessThanTail.next = greatThan;
        return lessThan;
    }

}

